# -*- coding: utf-8 -*-

def GoodIndex(keys):
    n = len(keys)
    m = n
    p = n
    last = keys[n-1]
    while n > 1:
        if keys[n-2] == last:
            p = n - 2
        n -= 1
    return m - p

def CountBadIndex(keys, bad):
    n = len(keys)
    j = n
    while j > 0:
        if keys[j-1] == bad:
            return n-j
        j -= 1
    return n

def CompareAndSearch(arr, keys):
    last_count = GoodIndex(keys)
    print('最后一个字符在前面的重复次数%d' % (last_count))
    FindNum = 0
    text_n = len(arr)
    k_n = len(keys)
    move = 0
    while move <= text_n-k_n:
        j = k_n-1
        print('移动位置%d' % (move))
        while j >= 0:
            if arr[move+j] != keys[j]:
                bad = arr[move+j]
                break
            j -= 1
        if j == -1:
            FindNum += 1
            move += k_n
        else:
            if j == k_n-1:
                print('坏字符为%s' %(bad))
                d = CountBadIndex(keys, bad)
                print('增加的坏字符长度为%d' % (d))
                move += d
            else:
                move += k_n - last_count
    print('模式串%s在文本串里找到次数%d' % (keys, FindNum))
    
keys = 'China'
s1 = 'I am from China. I ama student. I live in Tianjin China. I love Python. Are you from China?'
CompareAndSearch(s1, keys)
